#include <vector>
#include <queue>

using namespace std;

// 水位上升的泳池中游泳
// 在一个 n x n 的整数矩阵 grid 中
// 每一个方格的值 grid[i][j] 表示位置 (i, j) 的平台高度
// 当开始下雨时，在时间为 t 时，水池中的水位为 t
// 你可以从一个平台游向四周相邻的任意一个平台，但是前提是此时水位必须同时淹没这两个平台
// 假定你可以瞬间移动无限距离，也就是默认在方格内部游动是不耗时的
// 当然，在你游泳的时候你必须待在坐标方格里面。
// 你从坐标方格的左上平台 (0，0) 出发
// 返回 你到达坐标方格的右下平台 (n-1, n-1) 所需的最少时间
// 测试链接 : https://leetcode.cn/problems/swim-in-rising-water/

// 这道题使用并查集也能过，发挥一下你聪明的脑袋吧！！！

class Solution 
{
public:
    int swimInWater(vector<vector<int>>& grid) 
    {
        // 0：上，1：右，2：下，3：左
        int move[5] = {-1, 0, 1, 0, -1};
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));

        dist[0][0] = grid[0][0];
        vector<vector<bool>> visited(m, vector<bool>(n));
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        // first：源点到当前格子的代价，second：x * n + y
        // 这样做的目的是可以利用库中实现的比较器，不用自己重新实现
        // x * n + y 是表示点常用的技巧，将点（x, y）进行压缩
        // 记 pos = x * n + y，则 x = pos / n，y = pos % n 
        q.emplace(grid[0][0], 0);
        while(!q.empty())
        {
            // c 是去往点（x, y）的代价
            auto [c, pos] = q.top();
            q.pop();
            int x = pos / n, y = pos % n;
            if(visited[x][y]) continue;

            visited[x][y] = true;
            // 常见剪枝
            // 发现终点直接返回
            // 不用等都结束
            if(x == m - 1 && y == n - 1) return c;
            for(int i = 0; i < 4; ++i)
            {
                int nx = x + move[i], ny = y + move[i + 1];
                if(nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny])
                {
                    // nc 是去往点（nx, ny）的代价
                    // 至少都要 grid[nx][ny] 才能去往点（nx, ny）
                    int nc = max(c, grid[nx][ny]);
                    if(nc < dist[nx][ny])
                    {
                        dist[nx][ny] = nc;
                        q.emplace(nc, nx * n + ny);
                    }
                }
            }
        }

        return -1;
    }
};